//You are given two integer arrays nums1 and nums2 of lengths m and n 
//respectively. nums1 and nums2 represent the digits of two numbers. You are also given an 
//integer k. 
//
// Create the maximum number of length k <= m + n from digits of the two 
//numbers. The relative order of the digits from the same array must be preserved. 
//
// Return an array of the k digits representing the answer. 
//
// 
// Example 1: 
//
// 
//Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
//Output: [9,8,6,5,3]
// 
//
// Example 2: 
//
// 
//Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
//Output: [6,7,6,0,4]
// 
//
// Example 3: 
//
// 
//Input: nums1 = [3,9], nums2 = [8,9], k = 3
//Output: [9,8,9]
// 
//
// 
// Constraints: 
//
// 
// m == nums1.length 
// n == nums2.length 
// 1 <= m, n <= 500 
// 0 <= nums1[i], nums2[i] <= 9 
// 1 <= k <= m + n 
// 
// Related Topics 栈 贪心 单调栈 👍 434 👎 0

package leetcode.editor.cn;

public class P321CreateMaximumNumber {
    public static void main(String[] args) {
        Solution solution = new P321CreateMaximumNumber().new Solution();
        int[] nums1 = new int[]{3, 4, 6, 5};
        int[] nums2 = new int[]{9, 1, 2, 5, 8, 3};
        int k = 5;
        solution.maxNumber(nums1, nums2, k);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
/*方法一：单调栈
为了找到长度为 kk 的最大数，需要从两个数组中分别选出最大的子序列，这两个子序列的长度之和为 kk，然后将这两个子序列合并得到最大数。两个子序列的长度最小为 00，最大不能超过 kk 且不能超过对应的数组长度。

令数组 \textit{nums}_1nums
1
​
  的长度为 mm，数组 \textit{nums}_2nums
2
​
  的长度为 nn，则需要从数组 \textit{nums}_1nums
1
​
  中选出长度为 xx 的子序列，以及从数组 \textit{nums}_2nums
2
​
  中选出长度为 yy 的子序列，其中 x+y=kx+y=k，且满足 0 \le x \le m0≤x≤m 和 0 \le y \le n0≤y≤n。需要遍历所有可能的 xx 和 yy 的值，对于每一组 xx 和 yy 的值，得到最大数。在整个过程中维护可以通过拼接得到的最大数。

对于每一组 xx 和 yy 的值，得到最大数的过程分成两步，第一步是分别从两个数组中得到指定长度的最大子序列，第二步是将两个最大子序列合并。

第一步可以通过单调栈实现。单调栈满足从栈底到栈顶的元素单调递减，从左到右遍历数组，遍历过程中维护单调栈内的元素，需要保证遍历结束之后单调栈内的元素个数等于指定的最大子序列的长度。遍历结束之后，将从栈底到栈顶的元素依次拼接，即得到最大子序列。

第二步需要自定义比较方法。首先比较两个子序列的当前元素，如果两个当前元素不同，则选其中较大的元素作为下一个合并的元素，否则需要比较后面的所有元素才能决定选哪个元素作为下一个合并的元素。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/create-maximum-number/solution/pin-jie-zui-da-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
    class Solution {
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
            int m = nums1.length, n = nums2.length;
            int[] maxSubsequence = new int[k];
            int start = Math.max(0, k - n), end = Math.min(k, m);
            for (int i = start; i <= end; i++) {
                int[] subsequence1 = maxSubsequence(nums1, i);
                int[] subsequence2 = maxSubsequence(nums2, k - i);
                int[] curMaxSubsequence = merge(subsequence1, subsequence2);
                if (compare(curMaxSubsequence, 0, maxSubsequence, 0) > 0) {
                    System.arraycopy(curMaxSubsequence, 0, maxSubsequence, 0, k);
                }
            }
            return maxSubsequence;
        }

        public int[] maxSubsequence(int[] nums, int k) {
            int length = nums.length;
            int[] stack = new int[k];
            int top = -1;
            int remain = length - k;
            for (int i = 0; i < length; i++) {
                int num = nums[i];
                while (top >= 0 && stack[top] < num && remain > 0) {
                    top--;
                    remain--;
                }
                if (top < k - 1) {
                    stack[++top] = num;
                } else {
                    remain--;
                }
            }
            return stack;
        }

        public int[] merge(int[] subsequence1, int[] subsequence2) {
            int x = subsequence1.length, y = subsequence2.length;
            if (x == 0) {
                return subsequence2;
            }
            if (y == 0) {
                return subsequence1;
            }
            int mergeLength = x + y;
            int[] merged = new int[mergeLength];
            int index1 = 0, index2 = 0;
            for (int i = 0; i < mergeLength; i++) {
                if (compare(subsequence1, index1, subsequence2, index2) > 0) {
                    merged[i] = subsequence1[index1++];
                } else {
                    merged[i] = subsequence2[index2++];
                }
            }
            return merged;
        }

        public int compare(int[] subsequence1, int index1, int[] subsequence2, int index2) {
            int x = subsequence1.length, y = subsequence2.length;
            while (index1 < x && index2 < y) {
                int difference = subsequence1[index1] - subsequence2[index2];
                if (difference != 0) {
                    return difference;
                }
                index1++;
                index2++;
            }
            return (x - index1) - (y - index2);
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}